/**
 * 1043. 分隔数组以得到最大和
 * https://leetcode-cn.com/problems/partition-array-for-maximum-sum/
 */
public class Solutions_1043 {
    public static void main(String[] args) {
//        int[] arr = {1, 15, 7, 9, 2, 5, 10};
//        int k = 3;  // output: 84

//        int[] arr = {1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3};
//        int k = 4;  // output: 83

        int[] arr = {1};
        int k = 1;  // output: 1

        int result = maxSumAfterPartitioning(arr, k);
        System.out.println(result);
    }

    public static int maxSumAfterPartitioning(int[] arr, int k) {
        int len = arr.length;
        // dp[7] = 84：表示索引 7 - 1 = 6 上，分割后最大和为 84
        int[] dp = new int[len + 1];
        dp[0] = 0;

        for (int i = 1; i <= len; i++) {
            int maxVal = -1;
            int minIndex = Math.max(0, i - k);
            for (int j = i - 1; j >= minIndex; j--) {
                // 更新 [minIndx, j] 中的最大值
                maxVal = Math.max(maxVal, arr[j]);
                // 关键：在索引 j 之后，进行一次分割
                // dp[j] 处的最大和 + 子数组的最大和
                int sum = dp[j] + maxVal * (i - j);
                if (sum > dp[i]) {
                    // 更新 dp[i] 为最大结果
                    dp[i] = sum;
                }
            }
        }
        return dp[len];
    }
}
